# 给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。
# 例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。
#  返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
#
#  示例 1：
# 输入：digits = ["1","3","5","7"], n = 100
# 输出：20
# 解释：
# 可写出的 20 个数字是：
# 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
#
#  示例 2：
# 输入：digits = ["1","4","9"], n = 1000000000
# 输出：29523
# 解释：
# 我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
# 81 个四位数字，243 个五位数字，729 个六位数字，
# 2187 个七位数字，6561 个八位数字和 19683 个九位数字。
# 总共，可以使用D中的数字写出 29523 个整数。
#
#  示例 3:
# 输入：digits = ["7"], n = 8
# 输出：1
#
#  1 <= digits.length <= 9
#  digits[i].length == 1
#  digits[i] 是从 '1' 到 '9' 的数
#  digits 中的所有值都 不同
#  digits 按 非递减顺序 排列
#  1 <= n <= 10⁹
from typing import List


class Solution:
    def atMostNGivenDigitSet2(self, digits: List[str], n: int) -> int:
        """
        动态规划：
        首先求出少于 numLen 位能满足条件的所有数
        然后求用numLen能满足条件的数(动态规划)
        :param digits:
        :param n:
        :return:
        """
        numLen, digitSize, res, numStr = len(str(n)), len(digits), 0, str(n)
        for i in range(1, numLen):  # 首先求出少于 numLen 位能有多少数满足条件
            res += digitSize ** i

        # 然后计算满足条件的有 numLen 位数字的数的个数(动态规划)
        dp = [0] * (numLen + 1)  # dp[i] 表示小于等于 n 中最后 numLen - i 位数的合法数的个数
        dp[numLen] = 1
        for i in range(numLen - 1, -1, -1):
            tmp = int(numStr[i])
            for d in digits:
                if int(d) < tmp:
                    dp[i] += digitSize ** (numLen - i - 1)
                elif int(d) == tmp:
                    dp[i] += dp[i + 1]
        # print(dp)
        return res + dp[0]

    def atMostNGivenDigitSet1(self, digits: List[str], n: int) -> int:
        """
        暴力法(超时)：
        首先求出少于 numLen 位能满足条件的所有数
        然后求用numLen能满足条件的数(暴力法)
        :param digits:
        :param n:
        :return:
        """
        tmpDigits = set(map(int, digits))
        numLen, digitSize, tmp = 1, len(tmpDigits), n
        while tmp // 10 != 0:  # 求出 n 有多少位
            numLen += 1
            tmp //= 10
        res = 0
        for i in range(1, numLen):  # 首先求出少于 numLen 位能有多少数满足条件
            res += digitSize ** i

        def check(num: int) -> bool:
            # 写法一
            # last = num % 10  # 记录每次末位的数字
            # while last != num:
            #     if last not in tmpDigits:
            #         return False
            #     last = num % 10
            #     num //= 10
            # if last not in tmpDigits:
            #     return False

            # 写法二
            for _ in range(numLen):
                t = num % 10
                if t not in tmpDigits:
                    return False
                num //= 10
            return True
        # print(10 ** (numLen - 1), res, check(57), n)
        for i in range(10 ** (numLen - 1), n + 1):
            if check(i):
                res += 1
        return res

    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        return self.atMostNGivenDigitSet2(digits, n)


if __name__ == "__main__":
    digits, n = ["1", "3", "5", "7"], 100
    digits, n = ["1", "4", "9"], 1000000000
    # digits, n = ["7"], 8
    # digits, n = ["5", "7", "8"], 59
    # digits, n = ["1", "2", "3", "4", "5", " 6", "7", "8"], 8363065
    print(Solution().atMostNGivenDigitSet(digits, n))
